package org.example.oop.collection;

/**
 * org.example.oop.collection
 *
 * @author moLei
 * @description 红黑树
 * @since 2025/6/17
 */
public class RedBlackTree {

    /**
     * 定义节点类
     */
    class Node {
        /**
         * 数据域
         */
        int data;
        /**
         * 左节点
         */
        Node left;
        /**
         * 右节点
         */
        Node right;
        /**
         * 父节点
         */
        Node parent;
        /**
         * 颜色
         */
        boolean isRed;

        /**
         * 构造方法
         *
         * @param data 数据
         */
        public Node(int data) {
            this.data = data;
        }
    }

    /**
     * 根节点
     */
    private Node root;
    /**
     * 哨兵节点，也就是所有默认的叶子节点，final修饰的属性需要进行初始化
     */
    private final Node NIL;

    public RedBlackTree() {
        // 初始化给哨兵节点设置默认值，避免因为null引出的其他复杂操作，且所有的叶子节点都是NIL，避免其他额外开销
        NIL = new Node(0);
        // 设置哨兵节点为黑色
        NIL.isRed = false;
        // 将根节点指向NIL哨兵节点
        root = NIL;
    }

    /**
     * 红黑树的左旋操作，时间复杂度为O(1)
     * @param x 子树的引用节点
     */
    private void leftRotate(Node x) {
        // 获取子树的右节点
        Node y = x.right;
        // 将子树右节点的左节点指向子树
        x.right = y.left;
        // 判断y.left是否为NIL哨兵节点，如果不是的话需要更新y.left的父节点
        if (y.left != NIL) {
            y.left.parent = x;
        }
        // 将y的父引用指向x的父引用
        y.parent = x.parent;
        // 更新子树的引用节点指向的父节点，如果x的父节点为NIL，那么x就是根节点，将y设置为根节点
        if (x.parent == NIL) {
            root = y;
        } else if (x == x.parent.left) {
            // x不是根节点，且x为原父节点的左子节点，将x的父节点的左节点指向y
            x.parent.left = y;
        } else {
            // x为原父节点的右子节点，将x的父节点的右节点指向y
            x.parent.right = y;
        }

        // 让x指向y的左子节点
        y.left = x;
        // 更新x的父节点指向y
        x.parent = y;
    }

    /**
     * 红黑树的右旋操作
     * @param x 子树的引用节点
     */
    private void rightRotate(Node x) {
        // 获取引用节点的左节点
        Node y = x.left;
        // 将子树左节点的右节点指向子树的左节点
        x.left = y.right;
        // 判断y.right是否为NIL哨兵节点，如果不是的话需要更新y.right的父节点，将其指向x节点
        if (y.right != NIL) {
            y.right.parent = x;
        }
        // 将y的父节点指向x的父节点
        y.parent = x.parent;
        // 获取x的父节点，如果x为根节点，那么y就是根节点
        if (x.parent == NIL) {
            root = y;
        } else if (x == x.parent.right) {
            // 判断x为父节点的右子节点还是左子节点
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        // 让y的右节点指向x节点
        y.right = x;
        // 让x的父节点指向y
        x.parent = y;
    }

    /**
     * 插入操作
     * @param data 插入的数据
     */
    private void insert(int data) {
        // 根据数据创建节点
        Node node = new Node(data);
        // 初始化节点，新插入的节点必须是红色
        node.isRed = true;
        // 新节点没有子节点，全部指向NIL
        node.left = node.right = NIL;

        // 创建节点索引，获取当前节点和父节点
        Node current = root;
        Node parent = NIL;

        // 查找插入的位置
        while (current != NIL) {
            parent = current;
            // 判断是要向左节点查找还是右节点查找
            if (data < current.data) {
                // 插入的值小于当前节点的值，向左查找
                current = current.left;
            } else {
                // 插入的值大于当前节点的值，向右查找
                current = current.right;
            }
        }

        // 已经找到当前数据需要插入的位置，设置其指向的父节点位置
        node.parent = parent;
        // 判断当前红黑树是否有数据，该节点是否作为ROOT节点存在
        if (parent == NIL) {
            root = node;
        } else if (data < parent.data) {
            // 判断当前的插入数据放在父节点的左右，因为parent节点指向的当前位置为NIL，所以对于父节点来说并不知道这个子节点在自己的左还是右，所以需要判断
            parent.left = node;
        } else {
            parent.right = node;
        }

        // 插入新的节点可能会破坏红黑树的规则，所以需要进行修复，修复时需要从新插入的节点开始
        insertFixUp(node);
    }

    /**
     * 对红黑树进行修复，新插入节点可能导致违反红黑树规则，导致红黑树无法满足红黑树规则，所以需要进行修复
     * @param node
     */
    private void insertFixUp(Node node) {
        // 当前节点为新增的节点，新增节点的颜色为红色，所以需要判断和父节点颜色是否一样，一样的话就需要进行调整
        while (node.parent.isRed) {     // parent是红色，红红冲突
            if (node.parent == node.parent.parent.left) {       // 判断父节点在祖父节点的左侧
                // 获取叔叔节点
                Node uncle = node.parent.parent.right;
                // 判断叔叔节点是否为红色，如果是红色，那么就进行颜色调整，否则需要进行旋转操作
                if (uncle.isRed) {
                    // 调整颜色
                    node.parent.isRed = false;
                    uncle.isRed = false;
                    node.parent.parent.isRed = true;
                    // 设置当前节点为祖父节点
                    node = node.parent.parent;
                } else {
                    // 叔叔节点为黑色
                    // 判断当前节点在父节点的右侧，需要将节点变换为node在P节点的左侧，P节点在G节点的左侧
                    if (node == node.parent.right) {
                        // 设置当前节点为父节点
                        node = node.parent;
                        // 进行左旋，方便后续旋转，旋转之后，当前节点变为父节点的左节点
                        leftRotate(node);
                    }
                    // 调整父节点颜色
                    node.parent.isRed = false;
                    // 调整祖父节点颜色为红色
                    node.parent.parent.isRed = true;
                    // 对祖父节点进行右旋，这样原来的祖父节点是黑色的，现在调整为红色，对其右旋后其父节点处于原祖父节点的位置，这样的话对于祖父节点的父节点来说颜色就不会进行冲突
                    rightRotate(node.parent.parent);
                }
            } else {
                // P节点在G节点的右侧
                // 获取叔叔节点
                Node uncle = node.parent.parent.left;
                // U节点为红色
                if (uncle.isRed) {
                    // 变换颜色
                    node.parent.isRed = false;
                    uncle.isRed = false;
                    node.parent.parent.isRed = true;
                    // node和P、U节点都完成了变换，接下来就对祖父节点及其以上的节点进行调整
                    node = node.parent.parent;
                } else {
                    // 判断node节点在P节点的左侧，需要进行颜色调整进行选择，让其和P、G节点保持为一条直线
                    if (node == node.parent.left) {
                        node = node.parent;
                        rightRotate(node);
                    }
                    // node节点指向的是最后的叶子节点，如果通过了上面的右旋操作后，node为原P节点为红色
                    // 设置颜色
                    node.parent.isRed = false;
                    node.parent.parent.isRed = true;
                    // 进行左旋
                    leftRotate(node.parent.parent);
                }
            }
        }
        // 向上递归修复完成，将根节点设置为黑色
        root.isRed = false;
    }

}
